#pragma once

//公共的头文件
#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <thread>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;
//哈希桶的个数
static const size_t NUM_FREE_LIST = 208;
// PageCache一共几个桶
static const size_t NPAGES = 129;

static const size_t PAGE_SHIFT = 13;
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#define TCMalloc_PageMap TCMalloc_PageMap3<64 - PAGE_SHIFT>
#elif _WIN32
typedef size_t PAGE_ID;
#define TCMalloc_PageMap TCMalloc_PageMap1<32 - PAGE_SHIFT>
#else
typedef unsigned long long PAGE_ID;
#define TCMalloc_PageMap TCMalloc_PageMap3<64 - PAGE_SHIFT>
// linux
#endif //  _WIN64

#ifdef _WIN32
#include <windows.h>
#define TLS _declspec(thread)
#else
#include <unistd.h>
#define TLS __thread
#endif

//脱离malloc，直接调用Windows和Linux接口向堆要空间
inline static void *SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void *ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	void *ptr = sbrk(kpage * (1 << PAGE_SHIFT));
#endif
	if (ptr == nullptr)
	{
		throw std::bad_alloc();
	}
	return ptr;
}

inline static void SystemFree(void *ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	brk(ptr);
#endif
}

//取obj对象头上的4/8字节
static void *&GetNextObj(void *obj)
{
	return *(void **)obj;
}
//管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void *obj)
	{
		assert(obj);
		//头插
		GetNextObj(obj) = _freeList;
		_freeList = obj;

		++_size;
	}
	//头插一段范围，num表示这段范围中节点的个数
	void PushRange(void *start, void *end, size_t num)
	{
		GetNextObj(end) = _freeList;
		_freeList = start;

		////测试验证链表长度是否等于num
		// void* cur = start;
		// int i = 0;
		// while (cur)
		//{
		//	cur= GetNextObj(cur);
		//	i++;
		// }
		// if (num != i)
		//{
		//	int x = 0;
		// }

		_size += num;
	}
	void *Pop()
	{
		assert(_freeList);
		//头删
		void *obj = _freeList;
		_freeList = GetNextObj(obj);
		--_size;

		return obj;
	}
	//删除一段范围，num表示这段范围中节点的个数
	void PopRange(void *&start, void *&end, size_t num)
	{
		if (num < _size)
		{
			int x = 0;
		}

		assert(num >= _size);
		start = _freeList;
		end = start;
		for (size_t i = 0; i < num - 1; ++i)
		{
			if (end == nullptr)
			{
				int x = 0;
			}

			end = GetNextObj(end);
		}
		_freeList = GetNextObj(end);
		GetNextObj(end) = nullptr;
		_size -= num;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t &Size()
	{
		return _size;
	}
	size_t &GetMaxSize()
	{
		return _maxSize;
	}
	void *&GetStart()
	{
		return _freeList;
	}
	//清除当前的freeList
	void Clear()
	{
		_freeList = nullptr;
		_maxSize = 1;
		_size = 0;
	}

private:
	void *_freeList = nullptr;
	// ThreadCache每次从CentralCache获取多少个对象节点
	size_t _maxSize = 1;
	//当前节点的个数
	size_t _size = 0;
};

//使用类来实现计算对象大小的对其映射
//因为我们要使用哈希桶来管理链表，并且不能每个size都来一个链表，否则桶会非常多
//因此我们需要对size进行对齐，并且对齐数还要随着size进行改变，否则会产生很大的内存碎片浪费
class GetObjSizeClass
{
public:
	// 控制在12%左右的内碎片浪费
	// size的范围           对齐数          对应桶的范围
	// [1,128]				8byte对齐		freelist[0,16)
	// [129,1024]			16byte对齐		freelist[16,72)
	// [1025,8*1024]		128byte对齐		freelist[72,128)
	// [8*1024+1,64*1024]	1024byte对齐	freelist[128,184)

	//将size向上与alignNum对齐
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}
	//计算对齐后的值
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
		assert(false);
		return -1;
	}

	// 计算size向上取整后映射到哪个哈希桶（哈希桶的下标从0开始）
	static inline size_t _Index(size_t size, size_t align_shift)
	{
		return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	static inline size_t Index(size_t size)
	{
		assert(size <= MAX_BYTES);
		//每个区间有多少个自由链表
		static size_t groupArray[4] = {16, 56, 56, 56};
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + groupArray[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + groupArray[0] + groupArray[1];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8 * 1024, 10) + groupArray[0] + groupArray[1] + groupArray[2];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64 * 1024, 13) + groupArray[0] + groupArray[1] + groupArray[2] + groupArray[3];
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	// ThreadCache一次从CentralCache获取多少个对象
	// size越小，要的就越多,越大则要的越少
	static size_t NumMoveSize(int size)
	{
		assert(size > 0);

		int num = MAX_BYTES / size;
		//控制上限和下限
		if (num < 2)
		{
			num = 2;
		}
		if (num > 512)
		{
			num = 512;
		}
		return num;
	}

	//计算一次向系统获取几页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		//字节数除以一页的大小，求出几页
		size_t nPage = num * size;
		nPage >>= PAGE_SHIFT;

		if (nPage == 0)
		{
			return 1;
		}
		return nPage;
	}
};

//管理多个连续页大块内存跨度结构
struct Span
{
	//大块内存起始页的页号
	PAGE_ID _pageId = 0;
	//页数
	size_t _n = 0;
	//双向链表
	Span *_next = nullptr;
	Span *_prev = nullptr;
	//切好的小块内存，分配给thread cache的计数
	size_t _useCount = 0;
	//切好的小块内存，构成链表
	void *_freeList = nullptr;
	//是否在被CentralCache使用，如果正在被使用则无法在PageCache中合并
	bool _isUse = false;

	// Span切好的小对象的大小
	size_t _objSize = 0;
};
// span构成带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	void Insert(Span *pos, Span *newSpan)
	{
		assert(pos);
		assert(newSpan);
		Span *prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span *pos)
	{
		assert(pos);
		assert(pos != _head);
		Span *prev = pos->_prev;
		Span *next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
		//不需要删除pos，因为需要把span还给下一层
	}
	void PushFront(Span *span)
	{
		Insert(Begin(), span);
	}
	Span *PopFront()
	{
		Span *front = _head->_next;
		Erase(front);
		return front;
	}
	Span *Begin()
	{
		return _head->_next;
	}
	Span *End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	std::mutex &GetMutex()
	{
		return _mtx;
	}

private:
	Span *_head;
	//桶锁
	std::mutex _mtx;
};